#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
做法和nextPermuation
"""


class Solution:
    def previousPermuation(self, nums):
        '''
        [1,2, 3, 4] ------> [1, 2, 4, 3]
        [1, 3, 1, 2] ------> [1, 3, 2, 1]
        '''
        # self.origin = sorted(nums, reverse=True)        # 第一个的前一个是最后一个
        self.nums = nums
        self.n = len(nums)

        # ret = self.next(0)
        ret = self.inverse_find()
        if ret:
            remain_pre, idx = ret
            # return ret
            return self.nums[0:idx] + remain_pre
        else:
            return list(reversed(nums))     # 直接反序返回

    def inverse_find(self):
        '''
            方法2: 非递归
        '''
        for i in range(self.n-2, -1, -1):
            if self.nums[i] > self.nums[i+1]:
                return self.make_pre_remains(self.nums[i:]), i

        return None

    def make_pre_remains(self, remains):
        # print('remains %s' % remains)
        assert remains
        cur_ele = remains[0]
        remains.sort(reverse=True)

        pre_idx, pre_ele = self.sorted_pre_ele(remains, cur_ele)
        assert pre_idx and pre_ele

        del remains[pre_idx]
        return [pre_ele] + remains

    def sorted_pre_ele(self, l, value):
        # NOTE: 如果有相同元素也要考虑
        # print('l %s, value %s '% (l, value))
        for i, v in enumerate(l):
            if v < value:
                return i, v

        return -1, None


def main():
    print("start main")
    s = Solution()
    ret = s.previousPermuation([1,2,3, 4])
    # ret = s.previousPermutation([4,3,2,1])
    # ret = s.previousPermutation([1 ,3, 2, 3])
    print(ret)

if __name__ == "__main__":
    main()
